package searchStudy;

public class FindMedianSortedArrays {

    /**
     * LeetCode T4 寻找两个正序数组的中位数
     * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
     *
     * 查找中位数，就是使得前后的数字的个数相同
     *
     * 总结：该题困难的原因是：进行比较的数值不是给定（旋转数组）也并不存在与原数组（旋转数组查找最小值），二是存在与另一个数组（该题目）
     * @param args
     */
    public static void main(String[] args) {

    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //进行交换，使得nums1始终是长度小的，减小遍历次数
        if (nums1.length > nums2.length){
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        //获得数组的长度
        int m = nums1.length;
        int n = nums2.length;

        //数组一半的数量
        int total = (m + n + 1)/2;

        //在nums1的区间[0, m]里查找恰当的分割线
        //最终的结果是使得nums1[i - 1] <= nums2[j] && nums1[i]
        int left = 0;
        int right = m;

        //最终遍历到边界，利用了性质，利用二分查找将所有错误的结果都排除了
        while (left < right){
            //和能不能退出循环息息相关，中点取上界
            int i = (left + right + 1) >> 1;
            int j = total - i;
            //-1的都是左边的
            if (nums1[i - 1] > nums2[j]){
                //下一轮搜索的区间 [left, i - 1]
                right = i - 1;
            } else {
                //下一轮搜索区间，相等是有可能符合条件
                left = i;
            }
        }

        int i = left;
        int j = total - left;
        int num1LeftMax = i - 1 < 0? Integer.MIN_VALUE:nums1[i - 1];
        int num1RightMin = i >= m? Integer.MAX_VALUE:nums1[i];
        int num2LeftMax = j - 1 < 0 ? Integer.MIN_VALUE:nums2[j - 1];
        int num2RightMin = j >= n ?Integer.MAX_VALUE:nums2[j];

        if ((m + n) % 2 == 1){
            return (double) Integer.max(num1LeftMax, num2LeftMax);
        } else {
            return ((double)(Integer.max(num1LeftMax, num2LeftMax) + Integer.min(num1RightMin, num2RightMin)))/2;
        }
    }

//    public double findMedianSortedArrays(int[] nums1, int[] nums2){
//        int nums1_len = nums1.length;
//        int nums2_len = nums2.length;
//        int nums1_low = 0;
//        int nums1_high = nums1_len - 1;
//        int nums2_low = 0;
//        int nums2_high = nums2_len - 1;
//        int total = (nums1_len + nums2_len) / 2;
//        while (nums1_low <= nums1_high && nums2_low <= nums2_high){
//            int nums1_mid = (nums1_low + nums1_high) >> 1;
//            int nums2_mid = (nums2_low + nums2_high) >> 1;
//            //只取小的一部分，取到符合条件
//            if (nums1_mid > nums2_mid){
//                if (nums2_mid + nums1_low == total){
//                    if ((nums1_len + nums2_len)%2 == 1){
//                        return nums2[nums2_mid];
//                    } else {
//                        return (nums)
//                    }
//                }
//            } else {
//
//            }
//        }
//    }

}
